﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OnlineScheduling.DomainModel
{

    //kopczyk wzięty z jakiejś stronki, widać że fajnie zrobiony, generycznie w C#, to żal nie skorzystać
 

        /// <summary>
        /// heap data stucture, guaranteed O(nlog n), acts as a priority queue
        /// </summary>
        /// <typeparam name="TValue">
        /// </typeparam>
        public class Heap<TValue> where TValue : IComparable
        {
            // functions return if item not found
            public const int NOTFOUND = -1;
            // root offset
            const int ROOT = 0;
            // forward, backward step direction
            const int FORWARD = 1;
            const int BACKWARD = -FORWARD;
            // storage of values
            List<TValue> values = null;
            // allow parameterisation of ordering and (min/max heap)
            Comparison<TValue> comparison = null;

            /// <summary>
            /// creates a new heap, with ordering
            /// defined by T : IComparable
            /// </summary>
            public Heap()
            {
                values = new List<TValue>();
            }

            /// <summary>
            /// creates a new heap, with ordering
            /// defined by Comparison<T>
            /// </summary>
            /// <param name="comparison"></param>
            public Heap(Comparison<TValue> comparison)
                : this()
            {
                this.comparison = comparison;
            }

            /// <summary>
            /// return the value at offset position in the tree (pre-order traversal)
            /// </summary>
            /// <param name="position">offset in tree</param>
            /// <returns></returns>
            public TValue this[int position]
            {
                get
                {
                    return values[position];
                }
            }

            /// <summary>
            /// number of values in tree
            /// </summary>
            public int Count
            {
                get
                {
                    return Length();
                }
            }

            /// <summary>
            /// returns the offset of the parent
            /// </summary>
            /// <param name="position">the value position to find parent of</param>
            /// <returns>offset of parent in tree</returns>
            public int ParentOf(int position)
            {
                int result = NOTFOUND;
                if (position > 0)
                    result = ((position + 1) / 2) - 1;

                return result;
            }

            /// <summary>
            /// return the offset of the left child
            /// </summary>
            /// <param name="position">the value offset position to find the left child of</param>
            /// <returns>offset of left child in tree</returns>
            public int Left(int position)
            {
                int result = NOTFOUND;

                result = (position * 2) + 1;

                result = EnsureNotBeyond(result);

                return result;
            }

            /// <summary>
            /// return the offset of the right child
            /// </summary>
            /// <param name="position">the value offset position to find the right child of</param>
            /// <returns>offset of right child in tree</returns>
            public int Right(int position)
            {
                // right node is 1 more than the left
                int result = Left(position);

                if (result != NOTFOUND)
                    result++; // one position beyond left

                result = EnsureNotBeyond(result);

                return result;
            }

            /// <summary>
            /// returns the root value
            /// </summary>
            public TValue Root
            {
                get
                {
                    if (Length() == 0)
                        throw new InvalidOperationException("No items in heap");

                    return values[ROOT];
                }
            }

            /// <summary>
            /// returns the value with highest priority
            /// </summary>
            /// <returns>the value</returns>
            public TValue Pop()
            {
                TValue result = Root;

                int lastItem = EnsureNotBeyond(Length() - 1);

                if (Length() > 1)
                    values[ROOT] = values[lastItem];

                values.RemoveAt(lastItem);

                MaintainHeapProperty(FORWARD);

                return result;
            }


            public TValue PopAtSpecificPont(int index)
            {
                TValue result = this[index];

                int lastItem = EnsureNotBeyond(Length() - 1);

                if (Length() > 1)
                    values[index] = values[lastItem];

                values.RemoveAt(lastItem);

                MaintainHeapPropertyAtGivenPoint(FORWARD,index);

                return result;
            }

            /// <summary>
            /// add the value to the tree
            /// </summary>
            /// <param name="value">value to add</param>
            public void Push(TValue value)
            {
                values.Add(value);

                MaintainHeapProperty(BACKWARD);
            }

            /// <summary>
            /// number of nodes
            /// </summary>
            /// <returns>length</returns>
            private int Length()
            {
                return values.Count;
            }

            /// <summary>
            /// ensures a  position is not beyond the tree storage
            /// </summary>
            /// <param name="position">offset</param>
            /// <returns>offset, or NOTFOUND if out of bounds</returns>
            private int EnsureNotBeyond(int position)
            {
                if (position >= Length())
                    position = NOTFOUND;

                return position;
            }

            /// <summary>
            /// adjusts tree to ensure heap property maintained after a push or pop
            /// </summary>
            /// <param name="direction">FORWARD for push, BACKWARD if pop</param>
            private void MaintainHeapProperty(int direction)
            {
                int start = (direction == FORWARD) ? ROOT : Length();
                int end = (direction == FORWARD) ? Length() : NOTFOUND;

                for (int pos = start; pos != end; pos += direction)
                {
                    int left = Left(pos);
                    int right = Right(pos);

                    // ensure this value is greater than chidren
                    if (left != NOTFOUND && Compare(pos, left) < 0)
                        Swap(pos, left);
                    if (right != NOTFOUND && Compare(pos, right) < 0)
                        Swap(pos, right);
                }
            }


            private void MaintainHeapPropertyAtGivenPoint(int direction, int location)
            {
                int start = (direction == FORWARD) ? location : Length();
                int end = (direction == FORWARD) ? Length() : NOTFOUND;

                for (int pos = start; pos != end; pos += direction)
                {
                    int left = Left(pos);
                    int right = Right(pos);

                    // ensure this value is greater than chidren
                    if (left != NOTFOUND && Compare(pos, left) < 0)
                        Swap(pos, left);
                    if (right != NOTFOUND && Compare(pos, right) < 0)
                        Swap(pos, right);
                }
            }
            /// <summary>
            /// return integer indicating order
            /// </summary>
            /// <param name="first">offset of first</param>
            /// <param name="second">offset of second</param>
            /// <returns>.lt. zero=first,second;zero=first==second;.gt. zero=second,first</returns>
            private int Compare(int first, int second)
            {
                int result = 0;

                // if comparison delegate provided us it to compare
                if (comparison != null)
                    result = comparison(values[first], values[second]);
                else // default TValue compare
                    result = values[first].CompareTo(values[second]);

                return result;
            }

            /// <summary>
            /// swaps two offsets
            /// </summary>
            /// <param name="first">first offset</param>
            /// <param name="second">second offset</param>
            private void Swap(int first, int second)
            {
                TValue temp = values[first];
                values[first] = values[second];
                values[second] = temp;
            }

            public override string ToString()
            {
                StringBuilder sb = new StringBuilder();

                sb.Append("[");
                foreach (TValue value in values)
                    sb.Append(value.ToString());
                sb.Append("]");

                return sb.ToString();
            }
        }

    
}
